package com.yanceysong.codetop.s31_s40;


public class S40_Mid_165_比较版本号 {
    /**
     * 比较版本号
     * 题目链接: <a href="https://leetcode.cn/problems/compare-version-numbers/">...</a>
     * ------------------------------------------------------------
     * 题目描述:
     * 给定两个表示版本号的字符串 version1 和 version2, 比较它们的大小。
     * 版本号由一个或多个“修订号 revision”组成, 相邻修订号由点号 '.' 分隔, 每个修订号只包含数字, 可以包含前导零。
     * 例如:  "0", "1.0", "2.5.33", "01.002.0003" 都是合法版本号。
     * 规则: 从左到右逐段比较, 将每一段去除前导零后按十进制整数比较; 若某个版本较短, 缺失的部分视为 0。
     * 返回: version1 > version2 -> 1; version1 < version2 -> -1; 否则 -> 0。
     * ------------------------------------------------------------
     * 示例:
     * 1) version1 = "1.2", version2 = "1.10"  => -1  因为 2 < 10
     * 2) version1 = "1.01", version2 = "1.001" => 0  因为 01 == 001 == 1
     * 3) version1 = "1.0", version2 = "1.0.0.0" => 0 缺失段等同 0
     * 4) version1 = "2.0", version2 = "1.999" => 1 第一段 2 > 1
     * ------------------------------------------------------------
     * 核心洞察 (Key Insights):
     * 1. 逐段比较即可, 不需要整体转结构; 每段独立, 互不影响。
     * 2. "前导零" 不影响数值大小, Integer.parseInt / 手动去零 都可。
     * 3. 缺失的段统一按 0 处理 -> 等价于对齐较长数组。
     * 4. 可用 split + 遍历 (直观), 也可用双指针手动扫描 (节省额外数组对象, 更高效)。
     * ------------------------------------------------------------
     * 两种实现策略:
     * (A) split + parse: 代码直观, 适合面试快速写; 时间 O(n), 额外数组空间。
     * (B) 双指针扫描: 不创建字符串数组; 一次线性遍历, 时间 O(n), 额外空间 O(1)。
     * ------------------------------------------------------------
     * ASCII 对齐示意 ("1.02.003" vs "1.2.3.0"):
     * . version1:  1   .  02  .  003
     * .                |      |       |
     * . version2:  1   .   2  .   3  . 0
     * . 去零后:   [1]   [2]   [3]  vs  [1] [2] [3] [0]
     * . 末尾多出的 [0] 不影响结果 -> 相等
     * ------------------------------------------------------------
     * 复杂度分析:
     * 设两个版本号总长度为 n (字符数)。
     * - split 实现: 时间 O(n); 需要 O(k) 额外空间存数组 (k 为修订段数)。
     * - 双指针实现: 时间 O(n); 额外空间 O(1)。
     * ------------------------------------------------------------
     * 边界与测试关注点:
     * 1. 前导零: "000", "001", "01"。
     * 2. 长度差: "1" vs "1.0.0.0"。
     * 3. 立即分出胜负: "2" vs "1.999.999"。
     * 4. 全 0: "0.0.0" vs "0"。
     * 5. 最大整型边界 (题目保证 32 位 int 可容纳)。
     * 6. 随机一致性: 两种实现结果应一致。
     * ------------------------------------------------------------
     */
    public int compareVersion(String version1, String version2) {
        // 按点拆分为修订号数组 (需要转义点号)
        String[] segments1 = version1.split("\\.");
        String[] segments2 = version2.split("\\.");

        int maxLen = Math.max(segments1.length, segments2.length);
        for (int idx = 0; idx < maxLen; idx++) {
            int rev1 = (idx < segments1.length) ? Integer.parseInt(segments1[idx]) : 0; // parseInt 自动忽略前导零
            int rev2 = (idx < segments2.length) ? Integer.parseInt(segments2[idx]) : 0;
            if (rev1 > rev2) return 1;
            if (rev1 < rev2) return -1;
        }
        return 0; // 所有段相等
    }

    /**
     * 方法二: 双指针扫描 (不分割字符串)
     * 思路: 使用两个指针 i, j 分别扫描 version1 与 version2。
     * 每轮: 从当前位置读取一段 (到点或结尾), 去前导零后形成整数, 然后比较; 若不同直接返回。
     * 若全部相同, 返回 0。
     */
    public int compareVersionTwoPointers(String version1, String version2) {
        int n1 = version1.length();
        int n2 = version2.length();
        int i = 0, j = 0; // 双指针
        while (i < n1 || j < n2) {
            // 解析 version1 当前段
            int value1 = 0; // 若该轮没有字符则默认为0
            while (i < n1 && version1.charAt(i) == '0') { // 跳过前导零
                i++;
            }
            while (i < n1 && Character.isDigit(version1.charAt(i))) {
                value1 = value1 * 10 + (version1.charAt(i) - '0');
                i++;
            }
            // 跳过点
            if (i < n1 && version1.charAt(i) == '.') i++;

            // 解析 version2 当前段
            int value2 = 0;
            while (j < n2 && version2.charAt(j) == '0') { // 跳过前导零
                j++;
            }
            while (j < n2 && Character.isDigit(version2.charAt(j))) {
                value2 = value2 * 10 + (version2.charAt(j) - '0');
                j++;
            }
            if (j < n2 && version2.charAt(j) == '.') j++;

            if (value1 > value2) return 1;
            if (value1 < value2) return -1;
        }
        return 0;
    }

    /**
     * 快速对比两种实现是否一致 (调试/验证用)。
     */
    private void assertMethodsConsistent(String v1, String v2) {
        int r1 = compareVersion(v1, v2);
        int r2 = compareVersionTwoPointers(v1, v2);
        assert r1 == r2 : "两种实现结果不一致: " + v1 + " vs " + v2 + " -> " + r1 + " vs " + r2;
    }

    public static void main(String[] args) {
        S40_Mid_165_比较版本号 solution = new S40_Mid_165_比较版本号();

        System.out.println("=== 版本号比较算法测试开始 ===");

        // 原有详尽测试 (保持 + 调整说明)
        System.out.println("\n--- 测试1: 基础比较 \"1.2\" vs \"1.10\" ---");
        testBasicComparison1(solution);

        System.out.println("\n--- 测试2: 前导零处理 \"1.01\" vs \"1.001\" ---");
        testLeadingZeros(solution);

        System.out.println("\n--- 测试3: 长度不同 \"1.0\" vs \"1.0.0.0\" ---");
        testDifferentLengths(solution);

        System.out.println("\n--- 测试4: 边界情况测试 ---");
        testBoundaryCases(solution);

        System.out.println("\n--- 测试5: 单一修订号测试 ---");
        testSingleRevision(solution);

        System.out.println("\n--- 测试6: 大数修订号测试 ---");
        testLargeRevisionNumbers(solution);

        System.out.println("\n--- 测试7: 复杂前导零测试 ---");
        testComplexLeadingZeros(solution);

        System.out.println("\n--- 测试8: 多级版本号测试 ---");
        testMultiLevelVersions(solution);

        System.out.println("\n--- 测试9: 相同版本号测试 ---");
        testIdenticalVersions(solution);

        System.out.println("\n--- 测试10: 极端长度差异测试 ---");
        testExtremeLengthDifference(solution);

        System.out.println("\n--- 测试11: 双实现一致性随机测试 ---");
        testRandomConsistency(solution);

        System.out.println("\n--- 测试12: 末尾多余零等价测试 ---");
        testTrailingZerosEquivalence(solution);

        System.out.println("\n--- 测试13: 全零版本号测试 ---");
        testAllZeros(solution);

        System.out.println("\n--- 测试14: 构造较大输入性能冒烟 ---");
        testLargeInputPerformanceSmoke(solution);

        System.out.println("\n=== 所有测试完成 (若无断言失败即全部通过) ===");
    }

    // ========================= 以下为测试用例实现 =========================

    private static void testBasicComparison1(S40_Mid_165_比较版本号 solution) {
        String version1 = "1.2";
        String version2 = "1.10";
        System.out.println("输入: version1 = \"" + version1 + "\", version2 = \"" + version2 + "\"");
        printVersionAnalysis(version1, version2);
        int result = solution.compareVersion(version1, version2);
        int result2 = solution.compareVersionTwoPointers(version1, version2);
        System.out.println("compareVersion() -> " + result + " (期望: -1)");
        System.out.println("twoPointers()  -> " + result2 + " (期望: -1)");
        assert result == -1 && result2 == -1;
        System.out.println("✓ 基础比较测试通过");
    }

    private static void testLeadingZeros(S40_Mid_165_比较版本号 solution) {
        String version1 = "1.01";
        String version2 = "1.001";
        System.out.println("输入: version1 = \"" + version1 + "\", version2 = \"" + version2 + "\"");
        printVersionAnalysis(version1, version2);
        int r1 = solution.compareVersion(version1, version2);
        int r2 = solution.compareVersionTwoPointers(version1, version2);
        System.out.println("结果: " + r1 + ", " + r2 + " (期望: 0)");
        assert r1 == 0 && r2 == 0;
        System.out.println("✓ 前导零处理测试通过");
    }

    private static void testDifferentLengths(S40_Mid_165_比较版本号 solution) {
        String version1 = "1.0";
        String version2 = "1.0.0.0";
        printVersionAnalysis(version1, version2);
        int r1 = solution.compareVersion(version1, version2);
        int r2 = solution.compareVersionTwoPointers(version1, version2);
        System.out.println("结果: " + r1 + ", " + r2 + " (期望: 0)");
        assert r1 == 0 && r2 == 0;
        System.out.println("✓ 长度不同测试通过");
    }

    private static void testBoundaryCases(S40_Mid_165_比较版本号 solution) {
        assert solution.compareVersion("2.0", "1.9") == 1;
        assert solution.compareVersionTwoPointers("2.0", "1.9") == 1;
        assert solution.compareVersion("1.0", "1.0") == 0;
        assert solution.compareVersionTwoPointers("1.0", "1.0") == 0;
        assert solution.compareVersion("2", "1") == 1;
        assert solution.compareVersionTwoPointers("2", "1") == 1;
        System.out.println("✓ 边界情况测试通过");
    }

    private static void testSingleRevision(S40_Mid_165_比较版本号 solution) {
        assert solution.compareVersion("1", "2") == -1;
        assert solution.compareVersion("10", "2") == 1;
        assert solution.compareVersion("01", "1") == 0;
        assert solution.compareVersionTwoPointers("1", "2") == -1;
        assert solution.compareVersionTwoPointers("10", "2") == 1;
        assert solution.compareVersionTwoPointers("01", "1") == 0;
        System.out.println("✓ 单一修订号测试通过");
    }

    private static void testLargeRevisionNumbers(S40_Mid_165_比较版本号 solution) {
        assert solution.compareVersion("1.2147483647", "1.2147483646") == 1;
        assert solution.compareVersion("999999999.1", "1000000000.0") == -1;
        assert solution.compareVersionTwoPointers("1.2147483647", "1.2147483646") == 1;
        assert solution.compareVersionTwoPointers("999999999.1", "1000000000.0") == -1;
        System.out.println("✓ 大数修订号测试通过");
    }

    private static void testComplexLeadingZeros(S40_Mid_165_比较版本号 solution) {
        assert solution.compareVersion("1.0001", "1.1") == 0;
        assert solution.compareVersion("1.000", "1.0") == 0;
        assert solution.compareVersion("01.02.003", "1.2.3") == 0;
        assert solution.compareVersionTwoPointers("1.0001", "1.1") == 0;
        assert solution.compareVersionTwoPointers("1.000", "1.0") == 0;
        assert solution.compareVersionTwoPointers("01.02.003", "1.2.3") == 0;
        System.out.println("✓ 复杂前导零测试通过");
    }

    private static void testMultiLevelVersions(S40_Mid_165_比较版本号 solution) {
        assert solution.compareVersion("1.2.3.4", "1.2.3.5") == -1;
        assert solution.compareVersion("2.0.0.0", "1.9.9.9") == 1;
        assert solution.compareVersion("1.0.0", "1.0.0.0.0") == 0;
        assert solution.compareVersionTwoPointers("1.2.3.4", "1.2.3.5") == -1;
        assert solution.compareVersionTwoPointers("2.0.0.0", "1.9.9.9") == 1;
        assert solution.compareVersionTwoPointers("1.0.0", "1.0.0.0.0") == 0;
        System.out.println("✓ 多级版本号测试通过");
    }

    private static void testIdenticalVersions(S40_Mid_165_比较版本号 solution) {
        assert solution.compareVersion("1.2.3", "1.2.3") == 0;
        assert solution.compareVersion("01.02", "1.2") == 0;
        assert solution.compareVersion("1.0", "1") == 0;
        assert solution.compareVersionTwoPointers("1.2.3", "1.2.3") == 0;
        assert solution.compareVersionTwoPointers("01.02", "1.2") == 0;
        assert solution.compareVersionTwoPointers("1.0", "1") == 0;
        System.out.println("✓ 相同版本号测试通过");
    }

    private static void testExtremeLengthDifference(S40_Mid_165_比较版本号 solution) {
        assert solution.compareVersion("1", "1.0.0.0.0.0.0.0.0.0") == 0;
        assert solution.compareVersion("1", "1.0.0.0.0.0.0.0.0.1") == -1;
        assert solution.compareVersionTwoPointers("1", "1.0.0.0.0.0.0.0.0.0") == 0;
        assert solution.compareVersionTwoPointers("1", "1.0.0.0.0.0.0.0.0.1") == -1;
        System.out.println("✓ 极端长度差异测试通过");
    }

    private static void testRandomConsistency(S40_Mid_165_比较版本号 solution) {
        java.util.Random rand = new java.util.Random(42);
        String digits = "0123456789";
        for (int t = 0; t < 200; t++) {
            int segs1 = 1 + rand.nextInt(6);
            int segs2 = 1 + rand.nextInt(6);
            StringBuilder v1 = new StringBuilder();
            StringBuilder v2 = new StringBuilder();
            for (int i = 0; i < segs1; i++) {
                int len = 1 + rand.nextInt(3);
                for (int k = 0; k < len; k++) v1.append(digits.charAt(rand.nextInt(10)));
                if (i + 1 < segs1) v1.append('.');
            }
            for (int i = 0; i < segs2; i++) {
                int len = 1 + rand.nextInt(3);
                for (int k = 0; k < len; k++) v2.append(digits.charAt(rand.nextInt(10)));
                if (i + 1 < segs2) v2.append('.');
            }
            solution.assertMethodsConsistent(v1.toString(), v2.toString());
        }
        System.out.println("✓ 双实现随机一致性测试通过 (200组)");
    }

    private static void testTrailingZerosEquivalence(S40_Mid_165_比较版本号 solution) {
        String[][] cases = {
                {"1.0", "1"},
                {"1.0.0", "1"},
                {"1.0.0.0.0", "1"},
                {"0.0.0", "0"},
                {"10.0.0.0", "10"}
        };
        for (String[] c : cases) {
            assert solution.compareVersion(c[0], c[1]) == 0;
            assert solution.compareVersionTwoPointers(c[0], c[1]) == 0;
        }
        System.out.println("✓ 末尾多余零等价测试通过");
    }

    private static void testAllZeros(S40_Mid_165_比较版本号 solution) {
        assert solution.compareVersion("0", "0") == 0;
        assert solution.compareVersion("0.0", "0") == 0;
        assert solution.compareVersion("0.0.0.0", "0.0") == 0;
        assert solution.compareVersionTwoPointers("0", "0") == 0;
        assert solution.compareVersionTwoPointers("0.0", "0") == 0;
        assert solution.compareVersionTwoPointers("0.0.0.0", "0.0") == 0;
        System.out.println("✓ 全零版本号测试通过");
    }

    private static void testLargeInputPerformanceSmoke(S40_Mid_165_比较版本号 solution) {
        // 构造接近约束 (长度<=500) 的两个版本号
        StringBuilder a = new StringBuilder();
        StringBuilder b = new StringBuilder();
        for (int i = 0; i < 60; i++) { // 生成 60 段 (平均每段 ~1-2 位 + 点, 约 < 500 字符)
            a.append(i % 10);
            b.append(i % 10);
            if (i + 1 < 60) {
                a.append('.');
                b.append('.');
            }
        }
        // 修改末尾一段制造差异
        a.append(".9");
        b.append(".8");
        int r1 = solution.compareVersion(a.toString(), b.toString());
        int r2 = solution.compareVersionTwoPointers(a.toString(), b.toString());
        assert r1 == 1 && r2 == 1;
        System.out.println("✓ 大输入性能冒烟测试通过");
    }

    // 辅助: 打印拆分后修订号 (示意)
    private static void printVersionAnalysis(String version1, String version2) {
        String[] parts1 = version1.split("\\.");
        String[] parts2 = version2.split("\\.");
        System.out.print("version1 修订号: [");
        for (int i = 0; i < parts1.length; i++) {
            System.out.print(Integer.parseInt(parts1[i]));
            if (i < parts1.length - 1) System.out.print(", ");
        }
        System.out.println("]");

        System.out.print("version2 修订号: [");
        for (int i = 0; i < parts2.length; i++) {
            System.out.print(Integer.parseInt(parts2[i]));
            if (i < parts2.length - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
}
